package 中等.搜索.广度优先搜索;

import util.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/deepest-leaves-sum/
 */
public class 层数最深叶子节点的和_1302 {

    public static void main(String[] args) {

    }

    /**
     * 广度搜索取最后一层的数字和
     *
     * @param root
     * @return
     */
    public int deepestLeavesSum(TreeNode root) {
        int ans = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.addLast(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            int curSum = 0;
            while (size-- > 0) {
                TreeNode curNode = queue.pollFirst();
                curSum += curNode.val;
                if (curNode.right != null) queue.addLast(curNode.right);
                if (curNode.left != null) queue.addLast(curNode.left);
            }
            ans = curSum;
        }
        return ans;
    }

    private int maxDepth = 1;

    private int sum = 0;

    /**
     * 深度优先搜索
     * 维护全局变量 最大深度 maxDepth，最大深度数字和 sum
     * 记录每个节点的深度
     * curDepth<maxDepth  忽略
     * curDepth=maxDepth  sum+=val
     * curDepth>maxDepth  sum=val maxDepth=curDepth
     */
    public int deepestLeavesSum2(TreeNode root) {
        depthSearch(root, 1);
        return sum;
    }

    public void depthSearch(TreeNode node, int curDepth) {
        if (node == null) {
            return;
        }
        if (curDepth == maxDepth) {
            sum += node.val;
        } else if (curDepth > maxDepth) {
            sum = node.val;
            maxDepth = curDepth;
        }
        if (node.left != null) depthSearch(node.left, curDepth + 1);
        if (node.right != null) depthSearch(node.right, curDepth + 1);
    }


    // 第二次碰到
    private int maxDep;

    private int total;


    public int deepestLeavesSum3(TreeNode root) {
        dfs(root, 1);
        return total;
    }


    private void dfs(TreeNode node, int curDep) {
        if (node == null) {
            return;
        }
        if (curDep > maxDep) {
            maxDep = curDep;
            total = node.val;
        } else if (curDep == maxDep) {
            total += node.val;
        }
        dfs(node.left, curDep + 1);
        dfs(node.right, curDep + 1);
    }

}
